1. Field of the Invention
The invention relates to a technique for use in illustratively a transform coder for imparting robustness against burst (or similar) errors to data, such as image data, that exhibits local redundancy.
2. Description of the Prior Art
Image data, including still and motion images, is being increasingly manipulated in electronic form due, in part, to continued advances that are being made in the processing speed and sophistication available through digital circuitry. Generally, this manipulation involves, at least in part, for each separate image, either transmission or storage of a large matrix of digitized pixel values that collectively form that image.
Such a matrix (hereinafter referred to as an "image matrix") typically contains a substantial number of bits. For example, a digitized 256 level grayscale image containing 576 rows by 720 columns of eight-bit pixels, produces an image matrix that contains approximately 3.3 Mbits. Increasingly fine horizontal and vertical resolutions produce image matrices that contain larger numbers of bits. Color images, particularly those that are encoded to contain separate color coordinate matrices, contain substantially larger amounts of bits. Inasmuch as transmission bandwidth in a communications system is limited and digital storage capacity is finite, though often quite large, substantial efforts have been expended for some time in the art to devise various techniques that can be used to compress the information contained in an image matrix in order to appreciably reduce the number of bits that need to be transmitted or stored for each individual image.
A family of such compression techniques which is very well-known in the art, and that is showing increasing promise for use with digitized images, involves the use of the discrete cosine transform (DCT). This transform is attractive inasmuch as it, inter alia, only deals with real, and not imaginary, components and computationally is relatively easy and fast to implement. Moreover, the DCT has the advantageous property that most of the information for each image is encoded into relatively few transform coefficients that represent low spatial frequency information which, in general, approximately matches the response pattern of a human eye. Through use of the DCT, very good quality images, for a particular sampling scheme, can result from as little as 1 bit/pixel, while the same scheme with loss-less techniques typically require 4-5 bits/pixel.
In essence, compressing an image using the DCT often involves first horizontally and vertically partitioning a digitized image into separate blocks, each containing typically an 8-by-8 matrix of pixel values. The pixel values in each 8-by-8 block are then separately converted through the DCT into a corresponding 8-by-8 matrix of transform coefficients. Thereafter, each coefficient matrix is quantized to produce quantized DCT coefficients. The quantized coefficients are then converted through a suitable compression coder into an appropriate transmission symbol(s). The quantization process may involve scaling, rounding and/or truncation. If proper quantizing is used, any diminished high spatial frequency content in the image is rarely, if ever, apparent to a viewer. The compression coder is frequently an entropy coder which utilizes increasingly fewer bits to code coefficients for increasingly high spatial frequencies over those used to code the low frequency components. While the quantization process imparts some loss into the image and is irreversible, the coding process used within the compression coder itself is usually reversible and, for the most part, loss-less.
Specifically, for purposes of compression, the coding process (hereinafter referred to as "compression coding") typically involves first sequentially re-ordering the transform coefficients for each block into a so-called zig-zag sampling pattern starting with the DC coefficient (zero frequency component) in the upper left hand corner of the 8-by-8 coefficient matrix. Coefficients for increasing horizontal frequencies are situated horizontally to the right in the matrix; coefficients for increasing vertical frequencies are situated vertically down the matrix. This pattern eventually results in a one-dimensional array of DCT coefficients qualitatively arranged in order of ascending spatial frequencies. The AC coefficients are then encoded in their order of occurrence. A coding technique, such as a Huffman code, is used to efficiently encode, typically through run-length encoding, each run of zero coefficients in a block. This coding scheme also establishes amplitude categories for each non-zero coefficient and assigns a unique codeword to each such category. Each such non-zero DCT coefficient is encoded by a codeword, which specifies the appropriate amplitude category for that coefficient, and is followed by additional bits that identify a precise magnitude of the coefficient within that particular category. A separate codeword is assigned to an end-of-block code and is typically sent after the last non-zero coefficient in the block (unless that coefficient is at position 63). The DC coefficient is often encoded using one-dimensional Differential Pulse Code Modulation (DPCM) using the DC coefficient for the most recently occurring DCT transformed block as a prediction for the DC coefficient of the current transformed block. A Huffman code is frequently used to encode a difference value for the DC coefficient in terms of a unique codeword, that represents an amplitude category for that coefficient relative to a quasi-logarithmic scale, followed by additional bits that specify the coefficient value within that category. A transmission symbol is then formed of each codeword and any associated additional bits, if they exist. Inasmuch as the high order frequency coefficients are frequently zero-valued, increasingly fewer bits are used to encode each coefficient value for increasingly higher spatial frequencies. For additional details regarding the DCT, its use with image data and compression coding of transform coefficients, the reader is referred to K. R. Rao et al, Discrete Cosine Transform--Algorithms, Advantages, Applications (.COPYRGT.1990: Academic Press, San Diego) and N. Ahmed et al, "Discrete Cosine Transform", IEEE Transactions on Computers, January 1974, pages 90-93.
The resulting compression coded bits are then either transmitted through a communication channel to a far end receiver or stored on a suitable media, such as magnetic or optical, for subsequent playback. To construct a received or reconstruct a stored image, the process described above is essentially reversed, including inversion of the DCT, with compressed transformed data as input thereto and pixel data as resulting output therefrom.
Unfortunately, in "real world" environments, burst errors occur which corrupt the transmission or playback of image data. These errors are particularly problematic during data communication over a packet network. In such a network, compressed image data for a single image is sent as a number of successively occurring data packets. As these networks continue to proliferate to provide increasingly economic point-to-point data transport vehicles, more and more images are being transmitted as packet data. A burst (or similar) error, when it occurs and often due to a temporary failure in a communication channel itself or in transmission equipment connected thereto, will simply corrupt and destroy one or more successive packets of image data. As such, a localized portion of the reconstructed image will simply be lost. Hence, a reconstructed image will be depicted as containing a "hole" or blackened area corresponding to the corrupted data. The size of such a hole is directly related to the number of packets that has been lost. The greater the loss, the larger the hole and, conversely, the lesser the loss, the smaller the hole. While a complete loss of localized image data may be tolerated in reconstructed images used in some image processing applications, such a loss is simply intolerable in many other such applications. As such, these latter applications could not be effectively used with image data that underwent compression and experienced burst (or similar) errors. Burst errors can also occur during playback due to, for example, localized defects in the media that will permanently corrupt a portion of the stored image data or by virtue of a condition, such as dirt or the like on the media or an optical sensor, that temporarily obscures the sensed data.
Furthermore, it is expected that the art, in its continual efforts to conserve transmission bandwidth and maximize storage efficiencies, will continue to develop compression schemes to provide increasing amounts of compression for image data, including transform coefficient values. Naturally, as the degree of data compression used in coding image data increases, each packet or stored bit sequence will contain data for a spatially larger portion of the image. Unfortunately, as the compression increases, then a burst (or similar) error, even if it affects only a relatively small or even constant number of packets or stored bits, will consequently obliterate an increasingly larger portion of the image.
Thus a need exists in the art for a technique for use in transmission and/or storage of compressed data, particularly image (including both still and motion) data, and which is capable of imparting robustness to that data against burst or similar errors. Furthermore, such a technique should be suitable for use with transform coders, and particularly but not exclusively with those coders that utilize the DCT.